package com.fwpsl.graph;

import java.util.*;

/**
 * @author: 风戏fw
 * @date: 2024/4/5
 * @description: 图的遍历：深度优先和广度优先
 */
public class GraphSearch {

    /**
     * 图 - 广度优先遍历，通过队列和迭代来实现（先进先出），按层次输出
     * <p>
     * 广度优先遍历（Breadth-First Search, BFS）是一种用于遍历或搜索树或图的算法。
     * 这个算法从根（或任意节点）开始，探索最近的节点，然后转向下一个最近的节点。
     *
     * @param vertex
     */
    public static <T extends Comparable<T>> List<List<T>> bsf(Vertex<T> vertex) {
        List<List<T>> list = new ArrayList<>();
        if (vertex == null) {
            return list;
        }

        // 记录顶点是否已经被遍历
        Map<Vertex<T>, Boolean> visitedMap = new HashMap<>();
        // 存储待访问的节点
        Queue<Vertex<T>> queue = new LinkedList<>();
        queue.offer(vertex);
        while (!queue.isEmpty()) {
            List<T> sList = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                Vertex<T> tVertex = queue.poll();
                if (Boolean.TRUE.equals(visitedMap.get(tVertex))) {
                    continue;
                }

                sList.add(tVertex.data);
                visitedMap.put(tVertex, Boolean.TRUE);

                for (Edge<T> edge : tVertex.edges) {
                    queue.offer(edge.destination);
                }
            }

            if (sList.size() > 0) {
                list.add(sList);
            }
        }

        return list;
    }

    /**
     * 图 - 广度优先搜索，通过队列实现（先进先出），按层次查找
     *
     * @param root
     */
    public static <T extends Comparable<T>> Vertex<T> bsf(Vertex<T> root, T key) {
        if (root == null) {
            return null;
        }

        Queue<Vertex<T>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Vertex<T> tVertex = queue.poll();
            if (tVertex.data.equals(key)) {
                return tVertex;
            }

            for (Edge<T> edge : tVertex.edges) {
                queue.offer(edge.destination);
            }
        }
        return null;
    }

    /**
     * 图 - 深度优先遍历，通过栈和迭代来实现
     * <p>
     * 深度优先遍历（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。
     * 当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。
     *
     * @param root
     */
    public static <T extends Comparable<T>> List<T> dsf(Vertex<T> root) {
        List<T> list = new ArrayList<>();
        if (root == null) {
            return list;
        }

        // 记录顶点是否已经被遍历
        Map<Vertex<T>, Boolean> visitedMap = new HashMap<>();
        // 存储待访问的节点
        Deque<Vertex<T>> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Vertex<T> tVertex = stack.pop();
            if (Boolean.TRUE.equals(visitedMap.get(tVertex))) {
                continue;
            }

            list.add(tVertex.data);
            visitedMap.put(tVertex, Boolean.TRUE);
            for (int i = tVertex.edges.size() - 1; i >= 0; i--) {
                stack.push(tVertex.edges.get(i).destination);
            }
        }

        return list;
    }

    /**
     * 树 - 深度优先搜索，通过栈和迭代实现（后进先出）
     *
     * @param root
     * @param key
     * @return
     */
    public static <T extends Comparable<T>> Vertex<T> dsf(Vertex<T> root, T key) {
        if (root == null) {
            return null;
        }

        // 记录顶点是否已经被遍历
        Map<Vertex<T>, Boolean> visitedMap = new HashMap<>();
        // 存储待访问的节点
        Deque<Vertex<T>> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Vertex<T> tVertex = stack.pop();
            if (Boolean.TRUE.equals(visitedMap.get(tVertex))) {
                continue;
            }

            if (tVertex.data.equals(key)) {
                return tVertex;
            }

            visitedMap.put(tVertex, Boolean.TRUE);
            for (int i = tVertex.edges.size() - 1; i >= 0; i--) {
                stack.push(tVertex.edges.get(i).destination);
            }
        }
        return null;
    }

    public static <T> void printBsf(List<List<T>> list) {
        StringJoiner sj = new StringJoiner(",", "{", "}");

        for (List<T> l1 : list) {
            StringJoiner sj1 = new StringJoiner(",", "[", "]");
            for (T t : l1) {
                sj1.add(String.valueOf(t));
            }
            sj.add(sj1.toString());
        }

        System.out.println(sj.toString());
    }

    public static <T> void printDsf(List<T> list) {
        StringJoiner sj = new StringJoiner(",", "{", "}");

        for (T t : list) {
            sj.add(String.valueOf(t));
        }

        System.out.println(sj.toString());
    }

    public static void main(String[] args) {
        int[][] graphArr = {
                {0, 2, 3, 6, 0, 0},
                {2, 0, 0, 0, 4, 6},
                {3, 0, 0, 2, 0, 0},
                {6, 0, 2, 0, 1, 3},
                {0, 4, 0, 1, 0, 0},
                {0, 6, 0, 3, 0, 0}
        };
        Graph<Integer> graph = Graph.buildIntGraph(graphArr);
        Vertex<Integer> vertex_3 = graph.getVertex(3);

        printBsf(bsf(vertex_3));
        printDsf(dsf(vertex_3));

        Vertex<Integer> vertex_5 = graph.getVertex(5);
        System.out.println(bsf(vertex_3, Integer.valueOf(5)) == vertex_5);
        System.out.println(dsf(vertex_3, Integer.valueOf(5)) == vertex_5);
    }
}
